#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include <sys/time.h>
#include <stdio_ext.h>

/* if undefined, don't use a transposition table */
// #define TTABLE_MB 1024
// #define MOVE_PRUNING

//#define PRINT_SOLUTION

#define SAVE_SOLUTION_PATH

#define PROBLEMS 5000
#define MIN_SOLVED 75
#define MAX_TIME_LIMIT 512

int TIME_LIMIT = 1;

int goal_isfound;

int is_weight_defined = 0;

// the file that collects the training data
FILE *train_file;
  

struct timeval start_search, temp_search;


typedef struct {
  state_t state;
  int h_value;		/* if state has been searched before, we know
			   know a (potentially) better estimate of
			   the true distance to goal.  -1 if entry is unused */
} tt_entry_t;

typedef struct {
  int32_t size;		/* number of tt entries */
  tt_entry_t *entries;
} ttable_t;


uint64_t nodes_visited;


void clear_ttable( ttable_t *ttable )
{
  int32_t i;

  for( i = 0; i < ttable->size; ++i ) {

    ttable->entries[ i ].h_value = -1;
  }
}

ttable_t *new_ttable( const int32_t sizeMB )
{
  ttable_t *ttable;

  ttable = malloc( sizeof( *ttable ) );
  assert( ttable != NULL );

  ttable->size = (int64_t)sizeMB * 1048576 / sizeof( tt_entry_t );
  if( ttable->size < 1 ) {
    ttable->size = 1;
  }
  ttable->entries = malloc( sizeof( ttable->entries[ 0 ] ) * ttable->size );
  assert( ttable->entries != NULL );

  clear_ttable( ttable );

  return ttable;
}

/* update the transposition table with a new lower bound estimate */
void update_ttable( ttable_t *ttable, const state_t *state, const int h_value )
{
  int32_t idx;

  idx = hash_state( state ) % ttable->size;
  if( compare_states( state, &ttable->entries[ idx ].state ) == 0 ) {
    /* state is in table */

    if( h_value > ttable->entries[ idx ].h_value ) {
      /* h_value is a larger lower bound */

      ttable->entries[ idx ].h_value = h_value;
    }
  } else {
    /* state wasn't in table - overwrite */

    copy_state( &ttable->entries[ idx ].state, state );
    ttable->entries[ idx ].h_value = h_value;
  }
}

/* get the lower bound estimate for a state
   returns -1 if the state is not in the table */
int check_ttable( const ttable_t *ttable, const state_t *state )
{
  int32_t idx;

  idx = hash_state( state ) % ttable->size;
  if( compare_states( state, &ttable->entries[ idx ].state ) != 0 ) {
    /* state not in table */

    return -1;
  }

  return ttable->entries[ idx ].h_value;
}


/* generate a state using backwards moves from the goal
   returns non-zero on success, 0 on failure

   only uses the first goal state - if there are more goal states, you
   may want to change this to count them and then select a random goal

   NOTE THAT THIS MAY GENERATE SYNTACTICALLY CORRECT BUT INVALID
   STATES IF NOT ALL STATES ARE VALID AND AT LEAST ONE GAME RULE
   ASSIGNS A CONSTANT TO A STATE VARIABLE WHICH IS EITHER A LABEL OR
   UNSPECIFIED ON THE LEFT HAND SIDE */
int random_state( state_t *state ,int random_moves)
{
  int i, num_moves, j;
  func_ptr iter;
  int rules[ bw_max_children ];
  state_t child, *s, *c, *t;

  s = state;
  c = &child;

  first_goal_state( state, &i );
  for( i = 0; i < 100; ++i ) {

    num_moves = 0;
    init_bwd_iter( iter );
    while( ( rules[ num_moves ] = next_bwd_iter( iter, s ) ) >= 0 ) {
      ++num_moves;
    }

    if( num_moves == 0 ) {
      printf( "no moves at state " );
      print_state( stdout, s );
      printf( "\n" );
      if( i ) {
	printf( "parent " );
	print_state( stdout, c );
	printf( "\n" );
      }
      exit( -1 );
    }

    j = random() % num_moves;
    apply_bwd_rule( rules[ j ], s, c );
    t = s;
    s = c;
    c = t;
  }

  if( s != state ) {
    copy_state( state, s );
  }

  return 0;
}

int dfs( const state_t *state,
#ifdef PARENT_PRUNING
	 const state_t *parent_state,
#endif
#ifdef MOVE_PRUNING
	 const int history,
#endif
#ifdef TTABLE_MB
	 ttable_t *ttable,
#endif
	 const int rem_depth )
{
  int rule_used;
#ifdef MOVE_PRUNING
  int c_history;
#endif
  func_ptr iter;
  state_t child;

  ++nodes_visited;

#ifdef TTABLE_MB
  if( check_ttable( ttable, state
#ifdef HISTORY_TT
		    , history
#endif
		    ) > rem_depth ) {
    return 0;
  }
#endif
  if( rem_depth == 0 ) {

#ifdef DEPTH_LIMITED_SEARCH
    return 0;
#else
    if( is_goal( state ) ) {

#ifdef PRINT_SOLUTION
      print_state( stdout, state );
      printf( "\n" );
#endif
      return 1;
    } else {

      return 0;
    }
#endif
  }

  init_fwd_iter( iter );
  while( ( rule_used = next_fwd_iter( iter, state ) ) >= 0 ) {

#ifdef MOVE_PRUNING
    if( !fwd_rule_valid_for_history( history, rule_used ) ) {
      continue;
    }
    c_history = next_fwd_history( history, rule_used );
#endif

    apply_fwd_rule( rule_used, state, &child );

#ifdef PARENT_PRUNING
    if( compare_states( &child, parent_state ) == 0 ) {
      continue;
    }
#endif

    if( dfs( &child,
#ifdef PARENT_PRUNING
	     state,
#endif
#ifdef MOVE_PRUNING
	     c_history,
#endif
#ifdef TTABLE_MB
	     ttable,
#endif
	     rem_depth - 1 ) ) {

#ifdef PRINT_SOLUTION
      printf( "%s\n", fwd_rule_names[ rule_used ] );
      print_state( stdout, state );
      printf( "\n" );
#endif
      return 1;
    }
  }

#ifdef TTABLE_MB
#ifdef HISTORY_TT
  update_ttable( ttable, state, history, rem_depth + 1 );
#else
  update_ttable( ttable, state, rem_depth + 1 );
#endif
#endif

  return 0;
}

int dfs_heur( const abstraction_t *abst[],
	      const state_t *state,
#ifdef MOVE_PRUNING
	      const int history,
#endif
#ifdef TTABLE_MB
	      ttable_t *ttable,
#endif
	      const int rem_depth, int no_of_abstraction, float b[] )
{
  gettimeofday( &temp_search, NULL );
  temp_search.tv_sec -= start_search.tv_sec;
  temp_search.tv_usec -= start_search.tv_usec;
 
  if ((temp_search.tv_sec+temp_search.tv_usec/1000000) > TIME_LIMIT){
	return 1;
  }
  int rule_used, h;
#ifdef TTABLE_MB
  int h2;
#endif
#ifdef MOVE_PRUNING
  int c_history;
  funcp_ptr iter;
#else
  func_ptr iter;
#endif
  state_t child;

  ++nodes_visited;

  h = abstraction_lookup( abst, state, no_of_abstraction, b, is_weight_defined);
#ifdef TTABLE_MB
  h2 = check_ttable( ttable, state );
  if( h2 > h ) {
    h = h2;
  }
#endif
  if( h > rem_depth ) {
    return 0;
  } else if( rem_depth == 0 ) {

    if( is_goal( state ) ) {
      goal_isfound = 1;
#ifdef PRINT_SOLUTION
      print_state( stdout, state );
      printf( "\n" );
#endif

// no need to the heuristic value of goal
      return 1;
    } else {

      return 0;
    }
  }

  init_fwd_iter( iter );
  while( ( rule_used = next_fwd_iter( iter, state ) ) >= 0 ) {

#ifdef MOVE_PRUNING
    if( !fwd_rule_valid_for_history( history, rule_used ) ) {
      continue;
    }
    c_history = next_fwd_history( history, rule_used );
#endif

    apply_fwd_rule( rule_used, state, &child );

#ifdef PARENT_PRUNING
    if( compare_states( &child, parent_state ) == 0 ) {
      continue;
    }
#endif

    if( dfs_heur( abst, &child,
#ifdef MOVE_PRUNING
		   c_history,
#endif
#ifdef TTABLE_MB
		   ttable,
#endif
		   rem_depth - 1, no_of_abstraction , b) ) {

      if(goal_isfound){
#ifdef PRINT_SOLUTION
    	  printf( "%s\n", fwd_rule_names[ rule_used ] );
      	  print_state( stdout, state );
      	  printf( "\n" );
#endif

#ifdef SAVE_SOLUTION_PATH
      	  print_heuristic(abst, state, no_of_abstraction,train_file);	
          fprintf(train_file,"%d \n",rem_depth);
#endif
      }
 
      return 1;
    }
  }

#ifdef TTABLE_MB
  update_ttable( ttable, state, rem_depth + 1 );
#endif

  return 0;
}

int idastar( const abstraction_t *abst[], const state_t *state,
#ifdef TTABLE_MB
	     ttable_t *ttable,
#endif
	     int64_t *total_nodes, int no_of_abstractions, float b[] )
{
  gettimeofday( &start_search, NULL );
  int d, done;

  *total_nodes = 0;
  
  if( no_of_abstractions > 0/*abst != NULL*/ ) {
    d = abstraction_lookup( abst, state , no_of_abstractions, b , is_weight_defined);
  } else {
    d = 0;
  }
  for( ; 1; ++d ) {

    nodes_visited = 0;
    if( no_of_abstractions > 0/*abst != NULL*/ ) {

      done = dfs_heur( abst, state,
#ifdef MOVE_PRUNING
		       init_history,
#endif
#ifdef TTABLE_MB
		       ttable,
#endif
		       d , no_of_abstractions, b);
    } else {

      done = dfs( state,
#ifdef MOVE_PRUNING
		  init_history,
#endif
#ifdef TTABLE_MB
		  ttable,
#endif
		  d );
    }
    //printf( "search depth %d: %ld\n", d, nodes_visited );
    *total_nodes += nodes_visited;

    if( done ) {
      break;
    }
  }

  return d;
}

// This functions loads the weights that are combined with
// the heuristic values
void load_heurweights(float *b, int size, char* name){
	FILE *fin;
	fin = fopen( name,"r");
	
	if(fin == NULL){ // in the beginning no such file exists
		is_weight_defined = 0;
	        fprintf(stderr,"Weight file does %s not exist! \n",name);
		exit( -1 );				
	}
	else{
                is_weight_defined = 1;
                printf("Weights are: [");
		int i;
		for(i=0;i<size;i++){
			float number;
			int return_val = fscanf( fin, "%g", &number);
			if(return_val == EOF){
				fprintf(stderr,"There is not enough numbers in the weights file %s! \n",name);
				exit( -1 );
			}
			b[i] = number;
			printf("%g, ",number);
		}
		printf("]\n");
        }
}

int main( int argc, char **argv )
{
  state_t state; 

  if(argc < 2){
	fprintf( stderr, "The problems file needs to be specified! \n");
      	exit( -1 );
  }
  FILE *problem_file;

  if(argc < 3){
	fprintf( stderr, "Some weight file should be specified! \n");
	fprintf( stderr, "If the file does not exist, the max of the abstractions is considered! \n");
      	exit( -1 );
  }

  // load the weight file
  float b[argc-1];
  if(strcmp (argv[2],"-1") == 0)
	fprintf( stderr, "Max of the abstractions is considered as the heuristic! \n");
  else    	
	load_heurweights(b,(argc-2),argv[2]);   

  int64_t visited, total_visited;
  int trials, d, total_d;

  abstraction_t *abst[argc-2];

#ifdef TTABLE_MB
  ttable_t *ttable;
#endif
  struct timeval start, end, startprocess, endprocess;
  gettimeofday( &startprocess, NULL );

  
  /* read the map */
  int i;
  if( argc > 3 ) {
    for(i=1 ; i < argc-2 ; i++){
    	abst[i] = read_abstraction( argv[ i+2 ] );
    	if( abst[i] == NULL ) {
      		fprintf( stderr, "could not read abstraction file %s\n", argv[ i+2 ] );
      		exit( -1 );
    	}
    }
  } else {
    abst[0] = NULL;
  }


#ifdef TTABLE_MB
  ttable = new_ttable( TTABLE_MB );
#endif

  //srandom( 7 );
  total_d = 0;
  total_visited = 0;
  int total_solved = 0;
  
  int is_solved[PROBLEMS];
  for(i = 0 ; i < PROBLEMS ; i++){
	is_solved[i] = 0;
  }

  // number of bootstrap iterations
  int iteration_number = 0;

  // number of problems solved in each iteration
  int solved_this_iteration = 0;
  // each iteration of this while loop is one iteration of bootstrap

  train_file = fopen( "data","w");
  fprintf(train_file,"%d\n",argc-2);

  while(MIN_SOLVED < (PROBLEMS-total_solved)){

	problem_file = fopen( argv[1],"r");
	printf ("Iteration %d of boostrap: \n",iteration_number);
  	for( trials = 0; trials < PROBLEMS; ++trials ) {
   	 	goal_isfound = 0;
                
    		
		char line[ 1024 ];
		if(fgets( line, 1024, problem_file )==NULL){
			fprintf( stderr, "cannot read from the problem file!\n");
      		        exit( -1 );
		}
		
	        if (feof(problem_file))  
	           break; 
	        read_state(line, &state);
    		
		if(is_solved[trials])
			continue;
		
		printf( "problem %d: ", trials + 1 );
		print_state( stdout, &state );
    		gettimeofday( &start, NULL );
    		d = idastar( (const abstraction_t **)abst, &state,
#ifdef TTABLE_MB
			 ttable,
#endif
			 &visited , argc-3, b);
		gettimeofday( &end, NULL );
  		end.tv_sec -= start.tv_sec;
  		end.tv_usec -= start.tv_usec;
  		if( end.tv_usec < 0 ) {
   			end.tv_usec += 1000000;
    			--end.tv_sec;
 		}

		if(goal_isfound){
			is_solved[trials] = 1;
			solved_this_iteration ++;
			printf(" is solved within the %d seconds! solution depth = %d", TIME_LIMIT,d);
		}
		else{
			printf(" is unsolved!");
		}
		printf( "\n" );
		_flushlbf();
   		//printf( "depth %d nodes %lu\n", d, visited );
   	 	total_d += d;
    		total_visited += visited;
  	}

	fclose(problem_file);

	printf("%d of the %d remaining problems were solved in iteration %d\n",solved_this_iteration,(PROBLEMS-total_solved),iteration_number);
	if(solved_this_iteration > MIN_SOLVED){ // bootstrap has solved enough
		gettimeofday( &endprocess, NULL );
		endprocess.tv_sec -= startprocess.tv_sec;
		printf( "total time of this iteration: %zd seconds\n",endprocess.tv_sec);
		fclose(train_file);
		// update the weight function
		char* command1 = "make learning";
		if(system(command1) !=0){
			fprintf( stderr, "Making the learning part is failed!\n");
	      		exit( -1 );
		}

		char command2[1024];
		strcpy(command2,"./linreg ");
		char temp[100];
		sprintf( temp, "%d", iteration_number);
		strcat(command2,temp);
		if(system(command2) != 0){
			fprintf( stderr, "The learning part is failed!\n");
	      		exit( -1 );
		}

		sprintf( command2, "mv -f data data-%d", iteration_number);
		if(system(command2) != 0){
			fprintf( stderr, "The learning part is failed!\n");
	      		exit( -1 );
		}
		total_solved += solved_this_iteration;
		solved_this_iteration = 0;
		load_heurweights(b,argc-2,"weights.txt");
		train_file = fopen( "data","w");
		fprintf(train_file,"%d\n",(argc-2));
		iteration_number ++;
	}	
	else{
		printf("Time limit is increasing from %d",TIME_LIMIT);
		TIME_LIMIT *= 2;
		printf(" to %d.\n",TIME_LIMIT);
		if(TIME_LIMIT > MAX_TIME_LIMIT){
			fprintf( stderr, "Time limit exceeded the t_infty!\n");
			break;
		} 
	}
 }

 gettimeofday( &endprocess, NULL );
		endprocess.tv_sec -= startprocess.tv_sec;
  printf( "total time of the process: %zd seconds\n",endprocess.tv_sec);
  
 for(i= 1 ; i < argc-2 ; i++){
	  if( abst[i] != NULL ) {
    		destroy_abstraction( abst[i] );
  	}
  }

  return 0;
}
